//#include<iostream>
//#include<vector>
//using namespace std;
//void sort(vector<int>& _v,int _left,int _right)
//{
//
//	if (_left >= _right) return;
//	int _key = _v[rand() % (_right-_left + 1) + _left];
//
//	int i = _left;
//	int left = _left - 1;
//	int right = _right + 1;
//	while (i < right)
//	{
//		if (_v[i] < _key) swap(_v[i++], _v[++left]);
//		else if (_v[i] == _key) i++;
//		else  swap(_v[i], _v[--right]);
//	}
//
//	sort(_v,_left,left);
//	sort(_v,right,_right);
//}
//
//int main()
//{
//	srand(time(nullptr));
//	vector<int> _v{ 1,5,8,0,6,7,2,3,4,9 };
//	sort(_v,0,_v.size()-1);
//	for (auto i : _v)
//	{
//		cout << i << " ";
//	}
//
//	return 0;
//}